package com.base.greedy;

import java.util.*;

/**
 * @ClassName FindMaximizedCapital
 * @Description 502. IPO
 * 假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。
 * 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
 *
 * 给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
 *
 * 最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
 *
 * 总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
 *
 * 答案保证在 32 位有符号整数范围内
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ipo
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author li
 * Date 2021/9/8 19:13
 * Copyright
 **/
public class FindMaximizedCapital {
    /**
     * 1`根据 profits 和 capital 预处理出总的任务集合二元组，并根据「启动资金」进行升序排序；
     *
     * 2`每次决策前，将所有的启动资金不超过 w 的任务加入优先队列（根据利润排序的大根堆），然后从优先队列（根据利润排序的大根堆），将利润累加到 w；
     *
     * 3`循环步骤 2，直到达到 k 个任务，或者队列为空（当前资金不足以选任何任务）
     *
     * @param k 最多K个项目
     * @param w 启动资本
     * @param profits 项目的利润集合
     * @param capital 项目需要的资本集合
     * @return 最多资本
     */
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        List<int[]> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new int[]{capital[i],profits[i]});
        }
        Collections.sort(list,(a,b) -> a[0] -b[0]);
        //大根堆
        Queue<Integer> heap = new PriorityQueue<>((a,b) -> b-a);
        int iProfits = 0;
        while (k-->0){
            while (iProfits<n&&list.get(iProfits++)[0]<=w){
                heap.add(list.get(iProfits)[1]);
            }
            if (heap.isEmpty()){
                break;
            }
            w+=heap.poll();
        }
        return w;
    }
}
